//: [Previous](@previous)

/*:
 # 选择排序
 * 最好情况 O(n^2)
 * 最坏情况 O(n^2))
 * 平均时间复杂度 O(n^2))
 * 空间复杂度 0(1)
 
 1. 先找出最大的数放到最后一个位置
 2. 去掉最后一个 从剩下的数里面找出最大的数放到最后一个
 3. 重复执行1，2步
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func selectionSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    var nums = arr
    
    for i in 0..<nums.count {
        var minI = i
        for j in i..<nums.count {
            if nums[minI] > nums[j] {
                minI = j
            }
        }
        if minI != i {
            nums.swapAt(minI, i)
        }
    }
    return nums
}

print("选择排序后 \(selectionSort(numbers))")

//: [Next](@next)
